package com.yangzhe.algorithm.c036;

import java.util.*;

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    /**
     * 提交时把方法名改为levelOrder
     * 此方法为普通bfs，需要额外空间记录层级，此题不推荐
     * BFS（广度优先）遍历流程死记即可：
     * 1. 跟节点入队列
     * 2. 开始循环 队列不为空时
     * 2.1 弹出节点
     * 2.2 弹出节点左不为空 加入队列
     * 2.3 弹出节点右不为空 加入队列
     * 2.4 打印弹出节点
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) {
            Queue<TreeNode> queue = new ArrayDeque<>();
            Map<TreeNode, Integer> levels = new HashMap<>();
            queue.add(root);
            levels.put(root, 0);

            int lastPrintLevel = 0;
            List<Integer> lastPrintList = new ArrayList<>();
            while (!queue.isEmpty()) {
                TreeNode treeNode = queue.poll();
                int currentLevel = levels.get(treeNode);
                int nextLevel = currentLevel + 1;
                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                    levels.put(treeNode.left, nextLevel);
                }

                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                    levels.put(treeNode.right, nextLevel);
                }

                if (currentLevel == lastPrintLevel) {
                    lastPrintList.add(treeNode.val);
                } else {
                    result.add(lastPrintList);
                    lastPrintLevel = currentLevel;
                    lastPrintList = new ArrayList<>();
                    lastPrintList.add(treeNode.val);
                }
            }

            result.add(lastPrintList);
        }

        return result;
    }


    private static class MyQueue {
        private TreeNode[] queue = new TreeNode[2001];

        private int l, r = 0;

        public void add(TreeNode treeNode) {
            if (r == queue.length - 1) {
                return;
            }
            queue[r++] = treeNode;
        }

        public TreeNode poll() {
            if (l == r) {
                return null;
            }
            return queue[l++];
        }

        public boolean isEmpty() {
            return l == r;
        }

        public int size() {
            return r - l;
        }
    }

    /**
     * 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐
     * BFS（广度优先）优化了遍历流程，可以在过程中知道遍历的层级：
     * 1. 根节点加入队列
     * 3. 开始循环 队列不为空时
     * 3.1 记录队列size
     * 3.2 开始循环size次
     * 3.2.1 弹出节点
     * 3.2.2 左不为空 加入队列
     * 3.2.3 右不为空 加入队列
     * 3.2.4 打印弹出的节点
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) {
            MyQueue queue = new MyQueue();
            queue.add(root);
            while (!queue.isEmpty()) {
                // 每次进入新的循环时记录当前层有多少个
                int size = queue.size();
                // 当前层要打印的节点
                List<Integer> currentLevelList = new ArrayList<>();
                // 遍历当前层的节点，并将下一层的节点放入队列
                for (int i = 0; i < size; i++) {
                    TreeNode treeNode = queue.poll();
                    if (treeNode.left != null) {
                        queue.add(treeNode.left);
                    }

                    if (treeNode.right != null) {
                        queue.add(treeNode.right);
                    }

                    currentLevelList.add(treeNode.val);
                }

                result.add(currentLevelList);
            }
        }

        return result;
    }

}
